def find_combinations(prices, target=50000):
    """
    寻找所有商品数量的组合，使得总价正好等于目标金额（分）
    :param prices: 商品价格列表（单位：分）
    :param target: 目标金额（分），默认500元=50000分
    :return: 所有符合条件的组合列表，每个组合为数量列表（按商品顺序排列）
    """
    n = len(prices)
    combinations = []
    
    def backtrack(index, remaining, current):
        if index == n:
            if remaining == 0:
                combinations.append(current.copy())  # 直接保存数量列表
            return
        
        p = prices[index]
        max_count = min(remaining // p, 100)  # 最多买100件（可调整）
        
        for count in range(max_count + 1):
            current[index] = count
            new_remaining = remaining - count * p
            if new_remaining < 0:
                break
            backtrack(index + 1, new_remaining, current)
    
    current = [0] * n  # 初始化数量列表（长度为商品种类数）
    backtrack(0, target, current)
    return combinations


# ---------------------- 示例用法 ----------------------
if __name__ == "__main__":
    # 输入商品价格（单位：元），转换为分
    prices_yuan = [99, 199, 299]  # 可修改为你想购买的商品价格
    prices_fen = [int(p * 100) for p in prices_yuan]
    
    # 计算所有组合（结果为数量列表的集合）
    result = find_combinations(prices_fen)
    
    # 输出结果（列表形式）
    print(f"找到 {len(result)} 种组合：")
    for idx, combo in enumerate(result, 1):
        # 计算总价验证（可选）
        total_fen = sum(count * prices_fen[i] for i, count in enumerate(combo))
        total_yuan = total_fen // 100
        assert total_yuan == 500, f"组合 {idx} 总价异常：{total_yuan}元"
        
        # 直接打印数量列表（按商品顺序）
        print(f"组合 {idx}: {combo}")
